In the field of space communications, a convolutional code has been used by NASA's Voyager project for greater reliability in transmission of information. A Reed-Solomon (RS) code has also been used as a cyclic symbol error correcting code. And finally, a concatenated Reed-Solomon/convolutional encoding system has been adopted by the European Space Agency, National Aeronautics and Space Administration, and the Jet Propulsion Laboratory for the deep-space downlink. The performance of such a concatenated code scheme has been investigated by R. L. Miller, L. J. Deutsch and S. A. Butman, "On the Error Statistics of Viterbi Decoding and the Performance of Concatenated Codes," Jet Propulsion Laboratory, Pasadena, Calif., Sept. 1, 1981. It is shown that this concatenated channel provides a coding gain of almost 2 dB over a channel using only the convolutional code at a decoded bit error rate of 10.sup.-5.
One of the benefits of concatenated coding, and one of the main motivations for its adoption as a standard system, is that it provides for nearly error free communication links at fairly low signal power levels. This means that source data compression techniques can be used to help increase channel throughput without a substantial change in overall error rate. Data compression algorithms, while promising to remove substantial information redundancy are very sensitive to transmission errors. Study of a system using concatenated coding with data compression can be found in R. F. Rice, "End-to-End Image Information Rate Advantages of Various Alternative Communication Systems," Publication 82-61, Jet Propulsion Laboratory, Pasadena, Calif., Sept. 1, 1982.
A Reed-Solomon code is basically a polynomial code first presented in a paper by Irving S. Reed, et al., "Polynomial Codes Over Certain Finite Field," J. Soc. Industr. Appl. Math, Vol. 8, No. 2, pp. 300-304, June, 1960. For encoding, it is implemented by a circuit which performs polynomial division in a finite field. See U.S. Pat. No. 4,162,480 to Elwyn R. Berlekamp titled "Galois Field Computer." The major problem in designing a small encoder is the large quantity of hardware that is necessary. A conventional encoder for the (255, 223) RS code requires 32 finite field multipliers usually implemented as full parallel or table look-up multipliers. The use of either prohibits the implementation of the encoder on a single medium density VLSI chip.
Fortunately E. R. Berlekamp, "Bit-Serial Reed-Solomon Encoders," IEEE Trans. Inform. Theory, Vol. IT-28, No. 6, pp. 869-874, November 1982, describes a serial algorithm for finite field multiplication over a binary field. Berlekamp's algorithm requires only shifting and exclusive-OR operation. See also U.S. Pat. No. 4,410,989 titled "Bit Serial Encoder" to Berlekamp. Both references are incorporated herein by reference.
Recently, it has been known that this multiplication algorithm makes possible the design of a workable VLSI architecture and that a new dual-basis (255, 223) RS encoder can be realized readily on a single VLSI chip with NMOS technology. See I. S. Hsu, I. S. Reed, T. K. Truong, K. Wang, C. S. Yeh and L. J. Deutsch, "The VLSI Implementation of a Reed-Solomon Encoder Using Berlekamp's Bit-Serial Multiplier Algorithm," IEEE Trans. on Computers, Vol. C-33, No. 10, October 1984. This technical paper is also incorporated herein by reference.
In a concatenated coding system, inner decoder errors may occur in bursts, which are occasionally as long as several constraint lengths. The outer RS decoder remains undisturbed by errors which occur within a given 8-bit symbol (about one constraint length of the convolutional inner code). However, performance of the RS decoder is degraded by longer burst errors, i.e., errors occurring among successive symbols, as may occur in the operation of the inner decoder. As a consequence, interleaving the RS outer code is required for best performance, i.e., for preventing or minimizing correlated errors among successive symbols in the Viterbi inner decoder, as has been studied and reported by Joseph P. Odenwalder in a Final Report distributed by Linkabit Corporation of San Diego, Calif., under a contract for Jet Propulsion Laboratory dated Dec. 1, 1974, titled "Concatenated Reed-Solomon/Viterbi Channel Coding for Advanced Planetary Missions: Analysis, Simulations and Tests."
The concatenated coding system block diagram considered in that report included a symbol interleaving buffer in the transmitter and a symbol deinterleving buffer at the receiver generalized by FIG. 1 in this application. Interleaving is defined as dispersing the original sequence of symbols in an RS codeword or frame in a block of frames by reordering the sequence to include in the block the first symbol of every frame in the block followed by the second, third, etc., until all symbols of the block have been included. Deinterleaving is simply the inverse process. However, the process of interleaving would require too many components to be feasible for implementation on a single VLSI chip where that is required, that is in a system for communication from a spacecraft or a compact disk recorder, both of which may have a need for small size and/or weight, and high throughput which cannot tolerate the delays introduced by long leads interconnecting many chips.